package me.mingshan.leetcode;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * https://leetcode.cn/problems/sum-of-nodes-with-even-valued-grandparent/description/
 * <p>
 * 给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
 * <p>
 * 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
 * 如果不存在祖父节点值为偶数的节点，那么返回 0 。
 *
 * @author hanjuntao
 * @date 2025/9/1 0001
 */
public class L_1315_祖父节点值为偶数的节点和 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(7);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(7);
        root.left.left.left = new TreeNode(9);
        root.left.right.left = new TreeNode(1);
        root.left.right.right = new TreeNode(4);

        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(3);
        root.right.right.right = new TreeNode(5);

        System.out.println(sumEvenGrandparent2(root));  // 18
    }

    /**
     * 思路：
     * <p>
     * 1. 遍历所有路径
     * 2. 检测当前路径中是否有偶数祖父节点
     * <p>
     * 需要使用缓存，避免重复计算
     *
     * @param root
     * @return
     */
    public static int sumEvenGrandparent(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Set<TreeNode> cache = new HashSet<>();
        AtomicInteger result = new AtomicInteger(0);

        dfs(root, new ArrayList<>(), result, cache);
        return result.get();
    }

    private static void dfs(TreeNode root, List<TreeNode> s, AtomicInteger result, Set<TreeNode> cache) {
        if (root == null) {
            return;
        }

        s.add(root);

        if (root.left == null && root.right == null) {
            for (int i = 2; i < s.size(); i++) {
                TreeNode treeNode = s.get(i - 2);
                if (treeNode.val % 2 == 0) {
                    TreeNode treeNode1 = s.get(i);
                    if (!cache.contains(treeNode1)) {
                        cache.add(treeNode1);
                        result.addAndGet(treeNode1.val);
                    }
                }
            }

            s.remove(s.size() - 1);
            return;
        }

        //
        dfs(root.left, s, result, cache);
        dfs(root.right, s, result, cache);
        s.remove(s.size() - 1);
    }


    /**
     * <p>
     * 对于任意一颗子树，其满足条件的节点和为：
     * <p>
     * 其满足条件的节点和 = 左子树的满足条件的节点和 + 右子树满足条件的节点和 + （当前根节点满足条件 ？根节点值 ：0）
     * <p>
     * 如何知道当前根节点满足条件 ？
     * 需要知道其祖父节点是否为偶数。
     * <p>
     * 在dfs遍历过程中，需要将父节点和祖父节点的值传递给子节点
     *
     * @param root
     * @return
     */
    public static int sumEvenGrandparent2(TreeNode root) {
        return dfs(root, null, null);
    }

    /**
     * 在dfs中，需要将父节点和祖父节点的值传递给子节点
     *
     * @param root
     * @param pv   父节点的值
     * @param ppv  祖父节点的值
     * @return
     */
    private static int dfs(TreeNode root, Integer pv, Integer ppv) {
        if (root == null) {
            return 0;
        }

        int result = (ppv != null && ppv % 2 == 0 ? root.val : 0);

        ppv = pv;
        pv = root.val;

        int left = dfs(root.left, pv, ppv);
        int right = dfs(root.right, pv, ppv);

        return left + right + result;
    }
}
